package arrAndstr;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

/*
    57.插入区间
 */
public class T57 {

    public static void main(String[] args) {
        int[][] intervals = new int[][]{
                {2,6},
                {7,9}
        };
        int[] newInterval = new int[]{15,18};
        int[][] insert = insert(intervals, newInterval);
        for (int[] i : insert) {
            System.out.println(i[0] + "-" + i[1]);
        }
    }

    public static int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) return new int[][]{newInterval};

        int leftIndex = getLeftIndex(intervals, newInterval[0]);
        int rightIndex = getRightIndex(intervals, newInterval[1]);

        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < leftIndex; i++) {
            list.add(intervals[i]);
        }
        // 中间部分
        list.addAll(getMidList(intervals, leftIndex, rightIndex, newInterval));

        for (int i = rightIndex + 1; i < intervals.length; i++) {
            list.add(intervals[i]);
        }
        return list.toArray(new int[1][2]);
    }

    private static int getRightIndex(int[][] intervals, int i) {
        for (int j = intervals.length - 1; j >= 0; j--) {
            if (intervals[j][0] <= i) {
                return j;
            }
        }
        return 0;
    }

    private static int getLeftIndex(int[][] intervals, int i) {
        for (int j = 0; j < intervals.length; j++) {
            if (intervals[j][1] >= i) {
                return j;
            }
        }
        return intervals.length-1;
    }

    private static List<int[]> getMidList(int[][] intervals, int leftIndex, int rightIndex, int[] newInterval) {
        List<int[]> list = new ArrayList<>();
        list.add(intervals[leftIndex][0]<=newInterval[0] ? intervals[leftIndex] : newInterval);
        intervals[leftIndex] = intervals[leftIndex][0]<=newInterval[0] ? newInterval : intervals[leftIndex];
        for (int i = leftIndex; i <= rightIndex; i++) {
            int lastIndex = list.size() - 1;
            if (list.get(lastIndex)[1] >= intervals[i][0]
                    && list.get(lastIndex)[1] < intervals[i][1]) {
                list.set(lastIndex, new int[]{list.get(lastIndex)[0], intervals[i][1]});
            } else if (list.get(lastIndex)[1] < intervals[i][0]) {
                list.add(intervals[i]);
            }
        }
        return list;
    }
}
